package com.cet.algorithm.二叉树.验证二叉搜索树;

import java.util.Stack;

/**
 * @program: cet-practice
 * @description: 验证二叉搜索树
 * @author: 陈恩涛
 * @create: 2023-04-05 11:31
 **/
public class LC98 {

    public static void main(String[] args) {
        TreeNode root = new TreeNode(10, new TreeNode(5), new TreeNode(15, new TreeNode(6), new TreeNode(20)));
        System.out.println(isValidBST(root));
    }

    static TreeNode pre = null;

    /**
     * verify a binary tree is a BST , recursion solution
     * tips: 中序遍历的BST是个递增序列
     * @param root tree root node
     * @return true or false
     */
    static boolean isValidBST(TreeNode root) {
        if (root == null) {
            return true;
        }

        boolean left = isValidBST(root.left);

        if (pre != null && pre.val >= root.val) {
            return false;
        } else {
            pre = root; // 第一次会拿到二叉树最左边的节点
        }

        boolean right = isValidBST(root.right);

        return left && right;
    }

    /**
     * verify a binary tree is a BST , iteration solution
     * tips: 中序遍历的BST是个递增序列
     * @param root tree root node
     * @return true or false
     */
    static boolean isValidIterateBST(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        if (root == null) {
            return true;
        }
        stack.push(root);
        TreeNode cur = null;
        TreeNode pre = null;
        while (!stack.isEmpty()) {
            cur = stack.peek();
            if (cur != null) {
                stack.pop();
                if (cur.right != null) {
                    stack.push(cur.right);
                }
                stack.push(cur);
                stack.push(null);
                if (cur.left != null) {
                    stack.push(cur.left);
                }
            } else {
                stack.pop();
                cur = stack.pop();
                if (pre != null && pre.val >= cur.val) {
                    return false;
                }
                pre = cur;
            }
        }
        return true;
    }
}
